#ifndef _DEBRUIJN_GRAPH_H_
#define _DEBRUIJN_GRAPH_H_
#include "Global.h"
#include "Kmer.h"
//#include "SparseMapWrapper.h"
#include "FixedHashTree.h"
#include <vector>
#include <iostream>

//using GOOGLE_NAMESPACE::SparseMapWrapper;
using std::vector;
using std::cerr;
using std::endl;

/**
 * 	De bruijn graph. Stores all kmer information as a graph.
 * 	Reverse complements are also stored as a twin kmer.
 * 	This implementation guarantees kmer and twin will not be neighbors.
 *
 * @author	Tao Yu
 * @date	2011/3/23
 */
class DeBruijnGraph {
	//typedef SparseMapWrapper<CompressedKmer, KmerVertex, hash_kmer, eq_kmer> MyHashMap;
	typedef FixedHashTree<KmerVertex> MyHashMap;
public:
	typedef MyHashMap::iterator iterator;
private:
	MyHashMap m_htable; //< The underlying hash table storing kmers
	//KmerSet m_kmerSet; //< The set where kmers are finally stored.
	//GINT32 m_iter; //< Cursor.
	CompressedKmer tempNeigh;
	CompressedKmer tempKmer;
	/**
	 * 	Gets the predecessor with specified leading base.
	 *
	 * @author	Tao Yu
	 * @date	2011/3/23
	 *
	 * @param	kmer	The k-mer.
	 * @param vertex The vertex
	 * @param	base		One of the base defined in Global.h.
	 *
	 * @return	null if it fails, else the predecessor.
	 */
	KmerVertex* getPredecessor(const CompressedKmer& kmer, const KmerVertex* vertex, GBYTE base);

	/**
	 * 	Gets the successor with specified tailing base.
	 *
	 * @author	Tao Yu
	 * @date	2011/3/23
	 *
	 * @param	vertex	The vertex.
	 * @param	base  	One of the base defined in Global.h.
	 *
	 * @return	null if it fails, else the successor.
	 */
	KmerVertex* getSuccessor(const CompressedKmer& kmer, const KmerVertex* vertex, GBYTE base);
public:
	DeBruijnGraph() {} //< Only for serialization

	/**
	 * 	Constructor.
	 *
	 * @author	Tao Yu
	 * @date	2011/3/23
	 *
	 * @param	totalKmers	The total number of kmers including reverse complements.
	 */
	DeBruijnGraph(size_t bucketSizeArray[HASHTREE_SIZE]): m_htable(bucketSizeArray) {}

	~DeBruijnGraph() {
		cerr << "~DeBruijnGraph" <<endl;
		cerr << "exit ~DeBruijnGraph" <<endl;
	}

	/**
	 * 	Insert new node into internal hash table and update adjacent list of neighbors.
	 *
	 * @author	Tao Yu
	 * @date	2011/3/23
	 *
	 * @param [in, out]	vertex	Non-null, the vertex.
	 */
	void insertVertex(const CompressedKmer& kmer, KmerVertex* vertex);

	
	///**
	// * Remove a vertex.
	// * Clear its neighbor infomation.
	// * @param pos 
	// */
	//void removeVertex(iterator pos);

	/**
	 * 	Gets a vertex by its kmer content.
	 * 	This operation needs to look up the hash table.
	 *
	 * @author	Tao Yu
	 * @date	2011/3/23
	 *
	 * @param	kmer	The kmer content.
	 *
	 * @return	null if it fails, else the vertex.
	 */
	KmerVertex* getVertex(const CompressedKmer& kmer);

	/**
	 * 	Query if vertex of kmer exists.
	 *
	 * @author	Tao Yu
	 * @date	2011/3/23
	 *
	 * @param	kmer	The kmer.
	 *
	 * @return	true if vertex exists, false if not.
	 */
	bool hasVertex(const CompressedKmer& kmer);

	/**
	 * 	Gets the predecessors.
	 *
	 * @author	Tao Yu
	 * @date	2011/3/23
	 *
	 * @param	vertex	The vertex.
	 *
	 * @return	The list of predecessors.
	 */
	vector<KmerVertex*> getPredecessors(const CompressedKmer& kmer, const KmerVertex* vertex);

	/**
	 * 	Gets the successors.
	 *
	 * @author	Tao Yu
	 * @date	2011/3/23
	 *
	 * @param	vertex	The vertex.
	 *
	 * @return	The list of successors.
	 */
	vector<KmerVertex*> getSuccessors(const CompressedKmer& kmer, const KmerVertex* vertex);

	/**
	 * 	Gets the only predecessor. Be sure the vertex has only one predecessor first.
	 * 	Otherwise any predecessor can be returned.
	 *
	 * @author	Tao Yu
	 * @date	2011/3/23
	 *
	 * @param	vertex	The vertex.
	 *
	 * @return	The only predecessor.
	 */
	KmerVertex* getOnlyPredecessor(const CompressedKmer& kmer, const KmerVertex* vertex);

	/**
	 * 	Gets the only successor. Be sure the vertex has only one successor first.
	 * 	Otherwise any successor can be returned.
	 *
	 * @author	Tao Yu
	 * @date	2011/3/23
	 *
	 * @param	vertex	The vertex.
	 *
	 * @return The only successor.
	 */
	KmerVertex* getOnlySuccessor(const CompressedKmer& kmer, const KmerVertex* vertex);

	/**
	 * 	Gets the number of vertex without counting reverse complements.
	 *
	 * @author	Tao Yu
	 * @date	2011/3/23
	 *
	 * @return	The total number of vertex without counting reverse complements.
	 */
	GCOUNT_T numOfVertex();
	
	/**
	 * 	Gets a kmer vertex by identifier.
	 *
	 * @author	Tao Yu
	 * @date	2011/3/6
	 *
	 * @param	id	The identifier.
	 *
	 * @return	The vertex by identifier.
	 */
	KmerVertex* getVertexByID(GID_T Id) const;

	/**
	 * 	Gets the twin vertex.
	 *
	 * @author	Tao Yu
	 * @date	2011/4/2
	 *
	 * @param [in]	kmer
	 *
	 * @return	null if it fails, else the twin vertex.
	 */
	KmerVertex* getTwinVertex(const CompressedKmer& kmer);

	/**
	 * 	Indicates no more kmer will be inserted.
	 * 	This will clear internal hashtable.
	 *
	 * @author	Tao Yu
	 * @date	2011/3/23
	 */
	void finishBuilding();
	
	DeBruijnGraph::iterator begin()
	{
		return m_htable.begin();
	}

	DeBruijnGraph::iterator end()
	{
		return m_htable.end();
	}

	/**
	 * 	Writes data to disk.
	 *
	 * @author	Tao Yu
	 * @date	2011/4/2
	 *
	 * @param [in,out]	fp	If non-null, the fp.
	 *
	 * @return	true if it succeeds, false if it fails.
	 */
	bool write_data(FILE *fp);

	/**
	 * 	Reads data from disk.
	 *
	 * @author	Tao Yu
	 * @date	2011/4/2
	 *
	 * @param [in,out]	fp	If non-null, the fp.
	 *
	 * @return	true if it succeeds, false if it fails.
	 */
	bool read_data(FILE *fp);
};

#endif